package tasks.leetcode.算法通关;

import java.util.Arrays;

public class CoinChange {
    public static void main(String[] args) {
        int i = coinChange(new int[]{1, 2, 5}, 11);
        System.out.println(i);
    }

    /**
     * 322. 零钱兑换
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange(int[] coins, int amount) {
        if (amount <= 0) {
            return 0;
        }
        int dp[] = new int[amount + 1];
        Arrays.fill(dp, amount + 1);

        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                // 当前的金额 i一定是要大于等于coin的，不然就会有负数
                if (coin <= i) {
                    dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

}
